﻿//洛谷：P1706 全排列问题
//链接：https://www.luogu.com.cn/problem/P1706


//方法：深度优先搜索（DFS）
#include <iostream>
#include <vector>
using namespace std;

vector<int> path;                       // 存储当前路径的数组
bool check[10];                         // 标记是否使用过某个数字

// 深度优先搜索（DFS）函数
static void dfs(int n)
{
    // 当路径长度达到n时，输出当前路径
    if (path.size() == n)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%5d", path[j]);     // 格式化输出，确保输出对齐
        }

        cout << endl;
        return;
    }

    // 遍历1到n，递归生成排列
    for (int i = 1; i <= n; i++)
    {
        // 如果数字i没有被使用过，加入路径并继续递归
        if (check[i] == false)
        {
            path.push_back(i);          // 将当前数字添加到路径中
            check[i] = true;            // 标记数字i为已使用

            dfs(n);                     // 递归调用，继续生成排列

            path.pop_back();            // 回溯，移除当前数字
            check[i] = false;           // 取消数字i的使用标记
        }
    }
}

int main()
{
    int n = 0;
    cin >> n;                           // 输入数字n，表示需要排列的数字个数

    dfs(n);                             // 调用DFS生成并输出所有排列

    return 0;
}
//在这个递归的深度优先搜索（DFS）算法中，n代表的是你想要生成排列的数字个数，也就是排列的长度。
//这个值在整个递归过程中是恒定不变的，因为它决定了最终路径的长度，即排列应该包含多少个数字。
//
//当你在dfs函数中再次调用自身时，传递的参数仍然是n，这是因为每次递归调用都是为了尝试构建一个完整的、长度为n的排列。
//无论递归到了哪一层，目标都是要构造出一个长度为n的排列，所以不需要改变这个参数。
//
//具体来说，在每一次递归调用中：
//    · 如果当前路径path的长度等于n，则表示已经找到了一个完整的排列，此时应该输出这个排列并返回。
//    · 如果path的长度还没有达到n，那么继续尝试将未使用的数字加入到当前路径中，并对更新后的路径继续进行递归调用，直到找到所有可能的排列。
//因此，n作为递归函数的一个参数，它是在整个递归树中保持不变的，用于定义问题的规模和递归终止条件。
//而递归本身通过path.size()来判断是否达到了终止条件。